package a12_图论;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * <p>
 * a03_所有可达路径复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/3/11
 */
public class a03_所有可达路径复习1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int maxNum = scanner.nextInt();
        int totalSide = scanner.nextInt();

        int[][] sides = new int[maxNum+1][maxNum+1];
        for (int i = 0; i < totalSide; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            sides[x][y] = 1;
        }

//        int maxNum = 5;
//        int totalSide = 5;
//
//        int[][] sides = new int[maxNum+1][maxNum+1];
//        sides[1][3] = 1;
//        sides[3][5] = 1;
//        sides[1][2] = 1;
//        sides[2][4] = 1;
//        sides[4][5] = 1;

        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        path.add(1);

        dfs(result, path, sides, 1);

        if(result.isEmpty()){
            System.out.println(-1);
        }else {
            for (List<Integer> list : result) {
                for (int i = 0; i < list.size(); i++) {
                    System.out.print(list.get(i));
                    if(i != list.size()-1){
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }
    }

    private static void dfs(List<List<Integer>> result,
                     LinkedList<Integer> path,
                     int[][] sides,
                     int currentNum){

        if(currentNum == sides.length - 1){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 1; i < sides[currentNum].length; i++) {
            if(sides[currentNum][i] == 0){
                continue;
            }
            path.add(i);
            dfs(result, path, sides, i);
            path.removeLast();
        }
    }
}
